#include "stdafx.h"
#include "IndexRange.h"
#include "util.h"
#include "errhandle.h"
#include "memrec.h"
#include "GeneralException.h"

#define new DBG_NEW

tIndexRange::tIndexRange(): HeadIndex(0), EndIndex(0), ArraySize(0), 
	IndexPairArray(NULL), ActualSize(0)
{
}

tIndexRange::~tIndexRange()
{
	SAFE_DELETE(IndexPairArray);
}

tIndexRange::tIndexRange(tIndexRange & ir)
{
	HeadIndex = ir.HeadIndex;
	EndIndex = ir.EndIndex;
	ActualSize = ArraySize = ir.ArraySize;
	if (ArraySize != 0)
	{
		IndexPairArray = new UINT64[ArraySize];
		if (IndexPairArray == NULL)
			throw GeneralException(E_MEMALLOC_FAIL);
		memcpy(IndexPairArray, ir.IndexPairArray, ArraySize*sizeof(UINT64));
	}
}
void tIndexRange::operator= (tIndexRange & ir)
{
	ActualSize = ArraySize = ir.ArraySize;
	if (IndexPairArray) delete[] IndexPairArray;
	IndexPairArray = NULL;
	HeadIndex = EndIndex = 0;
	if (ArraySize != 0)
	{
		IndexPairArray = new UINT64[ArraySize];
		if (IndexPairArray == NULL)
			throw GeneralException(E_MEMALLOC_FAIL);
		memcpy(IndexPairArray, ir.IndexPairArray, ArraySize*sizeof(UINT64));
	}
	HeadIndex = ir.HeadIndex;
	EndIndex = ir.EndIndex;
}
void tIndexRange::Assign(int size, UINT64 * pArray)
{
	ActualSize = ArraySize = size;
	SAFE_DELETE(IndexPairArray);
	HeadIndex = EndIndex = 0;
	if (size != 0)
	{
		IndexPairArray = new UINT64[ArraySize];
		if (IndexPairArray == NULL)
			throw GeneralException(E_MEMALLOC_FAIL);
		memcpy(IndexPairArray, pArray, ArraySize* sizeof(UINT64));
		HeadIndex = IndexPairArray[0];
		EndIndex = IndexPairArray[ArraySize-1];
	}
}

void tIndexRange::InsertOne(UINT64 Index)
{
	unsigned int pos;
	// Find a position to insert this Index.
	for (pos = 0; pos < ArraySize; pos++)
	{
		if (Index <= IndexPairArray[pos])
			break;
	}
	
	// If pos is pointing to the end of a range pair, it mean it falls to
	// that range.
	if ((pos & 1) == 1)
	{
		//Ignore this insert action because it falls to the exist range.
	}
	else
	{
		// Here, the index should be added to range list, it may be merged to left
		// range or merged to right range or added as a isolated range item.
		if (pos < ArraySize && (IndexPairArray[pos] == Index || IndexPairArray[pos] == Index + 1))
		{
			// merge this index to right range pair.
			IndexPairArray[pos] = Index;
			if (pos > 0 && IndexPairArray[pos] == IndexPairArray[pos-1] + 1)
			{
				// merge left and right index range.
				MergeIndexRange(pos);
			}
		}
		else if (pos > 0 && IndexPairArray[pos-1] == Index - 1)
		{
			// merge this index to left range pair.
			IndexPairArray[pos-1] = Index;
			if (pos < ArraySize && IndexPairArray[pos] == IndexPairArray[pos-1] - 1)
			{
				// merge left and right index range.
				MergeIndexRange(pos);
			}
		}
		else
		{
			// insert a isolated rang pair between left range pair and right range pair.
			// just at this pos.
			InsertIsolatedRange(Index, pos);
		}
	}
}

void tIndexRange::IncreaseArray(int Count)
{
	UINT64* NewArray = new UINT64[Count + ActualSize];
	memset(NewArray, 0,  (ActualSize + Count) * sizeof(UINT64));
	memcpy(NewArray, IndexPairArray, ArraySize * sizeof(UINT64));
	ActualSize += Count;
	delete[] IndexPairArray;
	IndexPairArray = NewArray;
}

void tIndexRange::InsertIsolatedRange(UINT64 Index, int pos)
{
	// Check the space .
	if (ArraySize == ActualSize)
	{
		int inc_count = 10;
		IncreaseArray(2 * inc_count);
	}
	// move the data behind the pos.
	memmove(IndexPairArray+(pos+2), 
			IndexPairArray+pos, 
			(ArraySize - pos) * sizeof(UINT64));
	// Insert two value as index range pair.
	IndexPairArray[pos] = Index;
	IndexPairArray[pos+1] = Index;
	// Increase used array size.
	ArraySize += 2;
}

void tIndexRange::MergeIndexRange(int pos)
{
	IndexPairArray[pos-1] = IndexPairArray[pos+1];
	memmove(IndexPairArray+pos, IndexPairArray+pos+2, 
			(ArraySize - pos - 2) * sizeof(UINT64));
	ArraySize -= 2;
}

void tIndexRange::InsertPair(UINT64 start, UINT64 end)
{
	for (UINT64 i = start; i < end+1; i++)
	{
		InsertOne(i);
	}

	HeadIndex = IndexPairArray[0];
	EndIndex = IndexPairArray[ArraySize-1];
}

void tIndexRange::Reset()
{
	ArraySize = 0;
	ActualSize = 0;
	HeadIndex = 0;
	EndIndex = 0;
	SAFE_DELETE(IndexPairArray);
}